﻿// 买卖股票的最佳时机（含冷冻期）
//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
//给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
//
//设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票） :
//
//卖出股票后，你无法在第二天买入股票(即冷冻期为 1 天)。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
	int maxProfit(vector<int>& prices)
	{
		int n = prices.size();
		vector<vector<int>> dp(n, vector<int>(3));
		// 初始化
		dp[0][0] = -prices[0];
		for (int i = 1; i < n; i++)
		{
			// 自绘状态机
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
			dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
			dp[i][2] = dp[i - 1][0] + prices[i];
		}
		return max(dp[n - 1][1], dp[n - 1][2]);
	}
}